﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>

using namespace std;

// 摆动序列

// 1.动态规划
class Solution
{
public:
    int wiggleMaxLength(vector<int>& nums)
    {
        // f[i]:表示以i为结尾最后一个位置呈"上升"趋势的最长摆动子序列
        // g[i]:表示以i为结尾最后一个位置呈"下降"趋势的最长摆动子序列
        // 1.长度为1   f[i] = 1
        // 2.长度大于1  j(0--->i-1)中与最后一个进行组合，找到下降趋势的最大值
        // g[i]同理
        int n = nums.size();
        vector<int> f(n, 1);
        auto g = f;
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                    f[i] = max(g[j] + 1, f[i - 1]);
                else if (nums[j] > nums[i])
                    g[i] = max(f[j] + 1, g[i - 1]);

                ret = max(ret, max(f[i], g[i]));
            }
        }

        return ret;
    }
};

// 2.贪心算法
class Solution
{
public:
    int wiggleMaxLength(vector<int>& nums)
    {
        // 如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波⾕的个数即可
        int n = nums.size();
        if (n < 2)
            return n;
        // left 用于记录nums[i]位置左侧的趋势
        int ret = 0, left = 0;
        for (int i = 0; i < n - 1; i++)
        {
            // right记录nums[i]右侧的趋势
            int right = nums[i + 1] - nums[i];
            if (right == 0) continue;
            if (right * left <= 0)
                ret++;
            left = right;
        }

        // 当倒数第二数两项趋势相反，直接加入倒数第二个和最后一个
        // 最后一个数等于倒数第二个数，倒数第二个数不会加入，就需要加入最后一个数
        return ret + 1;
    }
};

// 最长递增子序列
// 1. 动态规划
class Solution
{
public:
    int lengthOfLIS(vector<int>& nums)
    {
        // dp[i]:表示以i位置为结尾的递增子序列的长度
        // 1.最后一个单独作为一个
        // 2.j:(0->i-1)与最后一个进行组合,找出最大值
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }

            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

// 2.贪心算法
class Solution
{
public:
    int lengthOfLIS(vector<int>& nums)
    {
        // 创建一个数组
        // 所有长度为x的递增子序列中，最后一个元素的最小值;
        // 所有大于等于nums[]的最小值的位置
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < n; i++)
        {
            // 如果能接在最后⼀个元素后⾯，直接放
            if (nums[i] > ret.back())
                ret.push_back(nums[i]);
            else
            {
                // ⼆分插⼊位置
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (ret[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }

        return ret.size();
    }
};

// 递增的三元子序列
// 1.动态规划--超时
class Solution
{
public:
    bool increasingTriplet(vector<int>& nums)
    {
        // dp[i]:表示以i位置为结尾的递增子序列的最长长度
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
        {
            for (int j = i; j >= 0; j--)
            {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
                if (dp[i] > 2) return true;
            }
        }

        return false;
    }
};

// 2.贪心算法
class Solution
{
public:
    bool increasingTriplet(vector<int>& nums)
    {
        // 和最长递增子序列的长度相似
        // 这里不使用数组而是两个变量
        int n = nums.size();
        int a = nums[0], b = INT_MAX;
        for (int i = 1; i < n; i++)
        {
            // 大于最后一个数,可以直接插入(数组的时候),此时数量为3
            if (nums[i] > b) return true;
            // 大于a则赋值为b
            else if (nums[i] > a) b = nums[i];
            else a = nums[i];
        }
        return false;
    }
};
int main()
{

	return 0;
}